{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Flips in Binary Tree to Get Result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中得到结果所需的最少翻转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定<strong>二叉树</strong>的根 <code>root</code>，具有以下属性:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>叶节点&nbsp;</strong>的值为 <code>0</code> 或 <code>1</code>，分别表示 <code>false</code> 和 <code>true</code>。</li>\n",
    "\t<li><strong>非叶节点</strong>的值为 <code>2</code>、<code>3</code>、<code>4</code>、<code>5</code>，分别表示布尔运算&nbsp;<code>OR</code>,&nbsp;<code>AND</code>,&nbsp;<code>XOR</code>,&nbsp;<code>NOT</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>您还将得到一个布尔型&nbsp;<code>result</code>，这是 <code>root</code>&nbsp;节点的期望&nbsp;<strong>评价</strong><strong>&nbsp;</strong>结果。</p>\n",
    "\n",
    "<p data-group=\"1-1\">对节点的评价计算如下:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果节点是叶节点，则评价是节点的&nbsp;<strong>值</strong>，即 <code>true</code> 或&nbsp;<code>false</code>.</li>\n",
    "\t<li>否则, 将其值的布尔运算应用于子节点的&nbsp;<strong>评价</strong>，该节点的&nbsp;<strong>评价&nbsp;</strong>即为布尔运算后的结果。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在一个操作中，您可以&nbsp;<strong>翻转&nbsp;</strong>一个叶节点，这将导致一个 <code>false</code>&nbsp;节点变为 <code>true</code>&nbsp;节点，一个 <code>true</code>&nbsp;节点变为 <code>false</code>&nbsp;节点。</p>\n",
    "\n",
    "<p>返回<em>需要执行的最小操作数，以使 </em><code>root</code><em>&nbsp;的</em><em>评价得到&nbsp;</em><code>result</code>。可以证明，总有办法达到 <code>result</code>。</p>\n",
    "\n",
    "<p data-group=\"1-1\"><strong>叶节点&nbsp;</strong>是没有子节点的节点。</p>\n",
    "\n",
    "<p>注意: <code>NOT</code> 节点只有左孩子或只有右孩子，但其他非叶节点同时拥有左孩子和右孩子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/20/operationstree.png\" style=\"width: 500px; height: 179px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [3,5,4,2,null,1,1,1,0], result = true\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "可以证明，至少需要翻转 2 个节点才能使树的 root 评价为 true。上面的图显示了实现这一目标的一种方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [0], result = false\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "树的 root 的评价已经为 false，所以 0 个节点必须翻转。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在 <code>[1, 10<sup>5</sup>]</code>&nbsp;范围内。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 5</code></li>\n",
    "\t<li><code>OR</code>, <code>AND</code>, <code>XOR</code>&nbsp;节点有&nbsp;<code>2</code> 个子节点。</li>\n",
    "\t<li><code>NOT</code> 只有一个&nbsp;<code>1</code> 子节点。</li>\n",
    "\t<li>叶节点的值为 <code>0</code> 或&nbsp;<code>1</code>.</li>\n",
    "\t<li>非叶节点的值为<code>2</code>, <code>3</code>, <code>4</code>,&nbsp;<code>5</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-flips-in-binary-tree-to-get-result](https://leetcode.cn/problems/minimum-flips-in-binary-tree-to-get-result/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-flips-in-binary-tree-to-get-result](https://leetcode.cn/problems/minimum-flips-in-binary-tree-to-get-result/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,4,2,null,1,1,1,0]\\ntrue', '[0]\\nfalse']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(node):\n",
    "            if node.val == 0 or node.val == 1:\n",
    "                node.b = node.val\n",
    "                return node.b\n",
    "            if node.val == 2:\n",
    "                node.b = dfs(node.left) | dfs(node.right)\n",
    "                return node.b\n",
    "            if node.val == 3:\n",
    "                node.b = dfs(node.left) & dfs(node.right)\n",
    "                return node.b\n",
    "            if node.val == 4:\n",
    "                node.b = dfs(node.left) ^ dfs(node.right)\n",
    "                return node.b\n",
    "            if node.val == 5:\n",
    "                if node.left:\n",
    "                    node.b = 1 - dfs(node.left)\n",
    "                else:\n",
    "                    node.b = 1 - dfs(node.right)\n",
    "                return node.b\n",
    "        dfs(root)\n",
    "        if root.b == result:\n",
    "            return 0\n",
    "        def dfs(node, target):\n",
    "            if node.b == target:\n",
    "                return 0\n",
    "            if node.val == 0 or node.val == 1:\n",
    "                return 1\n",
    "            if node.val == 2:\n",
    "                if target == 0:\n",
    "                    return dfs(node.left, 0) + dfs(node.right, 0)\n",
    "                else:\n",
    "                    return min(dfs(node.left, 1), dfs(node.right, 1))\n",
    "            if node.val == 3:\n",
    "                if target == 0:\n",
    "                    return min(dfs(node.left, 0), dfs(node.right, 0))\n",
    "                else:\n",
    "                    return dfs(node.left, 1) + dfs(node.right, 1)\n",
    "            if node.val == 4:\n",
    "                if target == 0:\n",
    "                    return min(dfs(node.left, 0) + dfs(node.right, 0), dfs(node.left, 1) + dfs(node.right, 1))\n",
    "                else:\n",
    "                    return min(dfs(node.left, 0) + dfs(node.right, 1), dfs(node.left, 1) + dfs(node.right, 0))\n",
    "            if node.val == 5:\n",
    "                if target == 0:\n",
    "                    if node.left:\n",
    "                        return dfs(node.left, 1)\n",
    "                    else:\n",
    "                        return dfs(node.right, 1)\n",
    "                else:\n",
    "                    if node.left:\n",
    "                        return dfs(node.left, 0)\n",
    "                    else:\n",
    "                        return dfs(node.right, 0)\n",
    "        return dfs(root, result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "\n",
    "        def dfs(nd: TreeNode):\n",
    "            if nd is None:\n",
    "                return None\n",
    "            if nd.left is None and nd.right is None:\n",
    "                return [nd.val, 1 - nd.val]\n",
    "            lt, rt = dfs(nd.left), dfs(nd.right)\n",
    "            match nd.val:\n",
    "                case 2: # or\n",
    "                    return [lt[0] + rt[0], min(lt[0] + rt[1], lt[1] + rt[0], lt[1] + rt[1])]\n",
    "                case 3: # and\n",
    "                    return [min(lt[0] + rt[0], lt[0] + rt[1], lt[1] + rt[0]), lt[1] + rt[1]]\n",
    "                case 4: # xor\n",
    "                    return [min(lt[0] + rt[0], lt[1] + rt[1]), min(lt[0] + rt[1], lt[1] + rt[0])]\n",
    "                case 5: # not\n",
    "                    if lt is None:\n",
    "                        return rt[::-1]\n",
    "                    else:\n",
    "                        return lt[::-1]\n",
    "        \n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root):\n",
    "            if root.val<2:\n",
    "                return [root.val,1-root.val]\n",
    "            elif root.val==5:\n",
    "                return dfs(root.left or root.right)[::-1]\n",
    "            else:\n",
    "                l0,l1 = dfs(root.left)\n",
    "                r0,r1 = dfs(root.right)\n",
    "                if root.val==2:\n",
    "                    return [l0+r0,min(l0+r1,l1+r0,l1+r1)]\n",
    "                elif root.val==3:\n",
    "                    return [min(l0+r1,l1+r0,l0+r0),l1+r1]\n",
    "                else:\n",
    "                    return [min(l0+r0,l1+r1),min(l1+r0,l0+r1)]\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root):\n",
    "            if root.val < 2:\n",
    "                return [root.val, 1 - root.val]\n",
    "            elif root.val == 5:\n",
    "                return dfs(root.left or root.right)[::-1]\n",
    "            else:\n",
    "                [l0, l1] = dfs(root.left)\n",
    "                [r0, r1] = dfs(root.right)\n",
    "                if root.val == 2:\n",
    "                    return [l0 + r0, min(l0 + r1, l1 + r1, l1 + r0)]\n",
    "                elif root.val == 3:\n",
    "                    return [min(l0 + r0, l0 + r1, l1 + r0), l1 + r1]\n",
    "                else:\n",
    "                    return [min(l0 + r0, l1 + r1), min(l0 + r1, l1 + r0)]\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: TreeNode, result: bool) -> int:\n",
    "\n",
    "        def dfs(rt):\n",
    "            if (rt.left is None) and (rt.right is None):\n",
    "                return rt.val, 1 - rt.val\n",
    "            if rt.val == 5:\n",
    "                if (rt.right is None):\n",
    "                    a, b = dfs(rt.left)\n",
    "                elif (rt.left is None):\n",
    "                    a, b = dfs(rt.right)\n",
    "                return b, a\n",
    "            la, lb = dfs(rt.left)\n",
    "            ra, rb = dfs(rt.right)\n",
    "            if rt.val == 2:\n",
    "                return la + ra, min(la + rb, lb + ra, lb + rb)\n",
    "            if rt.val == 3:\n",
    "                return min(la + ra, la + rb, lb + ra), lb + rb\n",
    "            if rt.val == 4:\n",
    "                return min(la + ra, lb + rb), min(la + rb, lb + ra)\n",
    "\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root):\n",
    "            if root.val == 0:\n",
    "                return 0, 1\n",
    "            if root.val == 1:\n",
    "                return 1, 0\n",
    "            if root.val == 5:\n",
    "                f, t = dfs(root.left or root.right)\n",
    "                return t, f\n",
    "            lf, lt = dfs(root.left)\n",
    "            rf, rt = dfs(root.right)\n",
    "            if root.val == 2:\n",
    "                return rf + lf, min(lt + rt, lt + rf, lf + rt)\n",
    "            if root.val == 3:\n",
    "                return min(rf + lf, lt + rf, lf + rt), lt + rt\n",
    "            if root.val == 4:\n",
    "                return min(lf + rf, lt + rt), min(lt + rf, lf + rt)\n",
    "        return dfs(root)[int(result)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root):\n",
    "            if root.val == 0:\n",
    "                return 1, 0\n",
    "            if root.val == 1:\n",
    "                return 0, 1\n",
    "            if root.val == 5:\n",
    "                t, f = dfs(root.left or root.right)\n",
    "                return f, t\n",
    "            lt, lf = dfs(root.left)\n",
    "            rt, rf = dfs(root.right)\n",
    "            if root.val == 2:\n",
    "                return min(lt + rt, lt + rf, lf + rt), rf + lf\n",
    "            if root.val == 3:\n",
    "                return lt + rt, min(rf + lf, lt + rf, lf + rt)\n",
    "            if root.val == 4:\n",
    "                return min(lt + rf, lf + rt), min(lf + rf, lt + rt)\n",
    "        print(dfs(root))\n",
    "        return dfs(root)[int(not result)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}\n",
    "INF = int(1e20)\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional['TreeNode'], result: bool) -> int:\n",
    "        \"\"\"树的叶子为操作数，树的非叶子为运算符，求叶子节点的最小翻转次数\"\"\"\n",
    "\n",
    "        def dfs(root: Optional['TreeNode']) -> List[int]:\n",
    "            \"\"\"返回(变为FALSE的最小操作次数,变为TRUE的最小操作次数)\"\"\"\n",
    "            if not root:\n",
    "                return [INF, INF]\n",
    "            if root.val in (0, 1):\n",
    "                return [int(root.val == 1), int(root.val == 0)]\n",
    "            if root.val == 5:\n",
    "                return dfs(root.left)[::-1] if root.left else dfs(root.right)[::-1]\n",
    "\n",
    "            res, leftRes, rightRes = [INF, INF], dfs(root.left), dfs(root.right)\n",
    "            for left, leftFlip in enumerate(leftRes):\n",
    "                for right, rigthFlip in enumerate(rightRes):\n",
    "                    value = MAPPING[root.val](left, right)\n",
    "                    res[value] = min(res[value], leftFlip + rigthFlip)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(root)[result & 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}\n",
    "INF = int(1e20)\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional['TreeNode'], result: bool) -> int:\n",
    "        \"\"\"树的叶子为操作数，树的非叶子为运算符，求叶子节点的最小翻转次数\"\"\"\n",
    "\n",
    "        def dfs(root: Optional['TreeNode']) -> List[int]:\n",
    "            \"\"\"返回(变为FALSE的最小操作次数,变为TRUE的最小操作次数)\"\"\"\n",
    "            if not root:\n",
    "                return [INF, INF]\n",
    "            if root.val in (0, 1):\n",
    "                return [int(root.val == 1), int(root.val == 0)]\n",
    "            if root.val == 5:\n",
    "                return dfs(root.left)[::-1] if root.left else dfs(root.right)[::-1]\n",
    "\n",
    "            res, leftRes, rightRes = [INF, INF], dfs(root.left), dfs(root.right)\n",
    "            for left, leftFlip in enumerate(leftRes):\n",
    "                for right, rigthFlip in enumerate(rightRes):\n",
    "                    value = MAPPING[root.val](left, right)\n",
    "                    res[value] = min(res[value], leftFlip + rigthFlip)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(root)[result & 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}\n",
    "INF = int(1e20)\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional['TreeNode'], result: bool) -> int:\n",
    "        \"\"\"树的叶子为操作数，树的非叶子为运算符，求叶子节点的最小翻转次数\"\"\"\n",
    "\n",
    "        def dfs(root: Optional['TreeNode']) -> List[int]:\n",
    "            \"\"\"返回(变为FALSE的最小操作次数,变为TRUE的最小操作次数)\"\"\"\n",
    "            if not root:\n",
    "                return [INF, INF]\n",
    "            if root.val in (0, 1):\n",
    "                return [int(root.val == 1), int(root.val == 0)]\n",
    "            if root.val == 5:\n",
    "                return dfs(root.left)[::-1] if root.left else dfs(root.right)[::-1]\n",
    "\n",
    "            res, leftRes, rightRes = [INF, INF], dfs(root.left), dfs(root.right)\n",
    "            for left, leftFlip in enumerate(leftRes):\n",
    "                for right, rigthFlip in enumerate(rightRes):\n",
    "                    value = MAPPING[root.val](left, right)\n",
    "                    res[value] = min(res[value], leftFlip + rigthFlip)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(root)[result & 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root):\n",
    "            if root.val < 2:\n",
    "                return [root.val, 1 - root.val]\n",
    "            elif root.val == 5:\n",
    "                return dfs(root.left or root.right)[::-1]\n",
    "            else:\n",
    "                [l0, l1] = dfs(root.left)\n",
    "                [r0, r1] = dfs(root.right)\n",
    "                if root.val == 2:\n",
    "                    return [l0 + r0, min(l0 + r1, l1 + r1, l1 + r0)]\n",
    "                elif root.val == 3:\n",
    "                    return [min(l0 + r0, l0 + r1, l1 + r0), l1 + r1]\n",
    "                else:\n",
    "                    return [min(l0 + r0, l1 + r1), min(l0 + r1, l1 + r0)]\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(u):\n",
    "            x = u.val\n",
    "            if x in [0,1]:\n",
    "                return x,x^1\n",
    "            if x==5:\n",
    "                return dfs(u.left or u.right)[::-1]\n",
    "            l0,l1 = dfs(u.left)\n",
    "            r0,r1 = dfs(u.right)\n",
    "            if x==2:\n",
    "                return l0+r0,min(l1+r1,l1+r0,l0+r1)\n",
    "            if x==3:\n",
    "                return min(l0+r0,l0+r1,l1+r0),l1+r1\n",
    "            return min(l0+r0,l1+r1),min(l0+r1,l1+r0)\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(u):\n",
    "            x = u.val\n",
    "            if x in [0,1]:\n",
    "                return x,x^1\n",
    "            if x==5:\n",
    "                return dfs(u.left or u.right)[::-1]\n",
    "            l0,l1 = dfs(u.left)\n",
    "            r0,r1 = dfs(u.right)\n",
    "            if x==2:\n",
    "                return l0+r0,min(l1+r1,l1+r0,l0+r1)\n",
    "            if x==3:\n",
    "                return min(l0+r0,l0+r1,l1+r0),l1+r1\n",
    "            return min(l0+r0,l1+r1),min(l0+r1,l1+r0)\n",
    "        return dfs(root)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:\n",
    "        def dfs(root: Optional[TreeNode]) -> (int, int):\n",
    "            if root is None:\n",
    "                return inf, inf\n",
    "            x = root.val\n",
    "            if x in (0, 1):\n",
    "                return x, x ^ 1\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            if x == 2:\n",
    "                return l[0] + r[0], min(l[0] + r[1], l[1] + r[0], l[1] + r[1])\n",
    "            if x == 3:\n",
    "                return min(l[0] + r[0], l[0] + r[1], l[1] + r[0]), l[1] + r[1]\n",
    "            if x == 4:\n",
    "                return min(l[0] + r[0], l[1] + r[1]), min(l[0] + r[1], l[1] + r[0])\n",
    "            return min(l[1], r[1]), min(l[0], r[0])\n",
    "        \n",
    "        return dfs(root)[int(result)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Optional\n",
    "from operator import or_, and_, xor, not_\n",
    "\n",
    "# 定义操作与其对应的函数\n",
    "MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}\n",
    "# 定义一个极大值作为初始代价\n",
    "INF = int(1e20)\n",
    "\n",
    "# 树节点定义\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def minimumFlips(self, root: Optional['TreeNode'], result: bool) -> int:\n",
    "        \"\"\"树的叶子为操作数，树的非叶子为运算符，求叶子节点的最小翻转次数\"\"\"\n",
    "\n",
    "        def dfs(root: Optional['TreeNode']) -> List[int]:\n",
    "            \"\"\"返回(变为FALSE的最小操作次数,变为TRUE的最小操作次数)\"\"\"\n",
    "            if not root:\n",
    "                return [INF, INF]\n",
    "            # 叶子节点（操作数）\n",
    "            if root.val in (0, 1):\n",
    "                return [int(root.val == 1), int(root.val == 0)]\n",
    "            # NOT操作\n",
    "            if root.val == 5:\n",
    "                return dfs(root.left)[::-1] if root.left else dfs(root.right)[::-1]\n",
    "            \n",
    "            # 初始化结果\n",
    "            res = [INF, INF]\n",
    "            # 左右子节点的结果\n",
    "            leftRes = dfs(root.left)\n",
    "            rightRes = dfs(root.right)\n",
    "\n",
    "            # 遍历左右子节点的所有可能组合\n",
    "            for left, leftFlip in enumerate(leftRes):\n",
    "                for right, rigthFlip in enumerate(rightRes):\n",
    "                    value = MAPPING[root.val](left, right)\n",
    "                    res[value] = min(res[value], leftFlip + rigthFlip)\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return dfs(root)[result & 1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
